#include <stdio.h>
#include <stdlib.h>

#define pseudoprime_count 2058
int pseudoprime_list[pseudoprime_count] =
{
341, 561, 645, 1105, 1387, 1729, 1905, 2047,
2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681,
5461, 6601, 7957, 8321, 8481, 8911, 10261, 10585,
11305, 12801, 13741, 13747, 13981, 14491, 15709, 15841,
16705, 18705, 18721, 19951, 23001, 23377, 25761, 29341,
30121, 30889, 31417, 31609, 31621, 33153, 34945, 35333,
39865, 41041, 41665, 42799, 46657, 49141, 49981, 52633,
55245, 57421, 60701, 60787, 62745, 63973, 65077, 65281,
68101, 72885, 74665, 75361, 80581, 83333, 83665, 85489,
87249, 88357, 88561, 90751, 91001, 93961, 101101, 104653,
107185, 113201, 115921, 121465, 123251, 126217, 129889, 129921,
130561, 137149, 149281, 150851, 154101, 157641, 158369, 162193,
162401, 164737, 172081, 176149, 181901, 188057, 188461, 194221,
196021, 196093, 204001, 206601, 208465, 212421, 215265, 215749,
219781, 220729, 223345, 226801, 228241, 233017, 241001, 249841,
252601, 253241, 256999, 258511, 264773, 266305, 271951, 272251,
275887, 276013, 278545, 280601, 282133, 284581, 285541, 289941,
294271, 294409, 314821, 318361, 323713, 332949, 334153, 340561,
341497, 348161, 357761, 367081, 387731, 390937, 396271, 399001,
401401, 410041, 422659, 423793, 427233, 435671, 443719, 448921,
449065, 451905, 452051, 458989, 464185, 476971, 481573, 486737,
488881, 489997, 493697, 493885, 512461, 513629, 514447, 526593,
530881, 534061, 552721, 556169, 563473, 574561, 574861, 580337,
582289, 587861, 588745, 604117, 611701, 617093, 622909, 625921,
635401, 642001, 647089, 653333, 656601, 657901, 658801, 665281,
665333, 665401, 670033, 672487, 679729, 680627, 683761, 688213,
710533, 711361, 721801, 722201, 722261, 729061, 738541, 741751,
742813, 743665, 745889, 748657, 757945, 769567, 769757, 786961,
800605, 818201, 825265, 831405, 838201, 838861, 841681, 847261,
852481, 852841, 873181, 875161, 877099, 898705, 915981, 916327,
934021, 950797, 976873, 983401, 997633, 1004653, 1016801, 1018921,
1023121, 1024651, 1033669, 1050985, 1052503, 1052929, 1053761, 1064053,
1073021, 1082401, 1082809, 1092547, 1093417, 1104349, 1106785, 1109461,
1128121, 1132657, 1139281, 1141141, 1145257, 1152271, 1157689, 1168513,
1193221, 1194649, 1207361, 1246785, 1251949, 1252697, 1275681, 1277179,
1293337, 1302451, 1306801, 1325843, 1333333, 1357441, 1357621, 1373653,
1394185, 1397419, 1398101, 1419607, 1433407, 1441091, 1457773, 1459927,
1461241, 1463749, 1472065, 1472353, 1472505, 1485177, 1489665, 1493857,
1500661, 1507561, 1507963, 1509709, 1520905, 1529185, 1530787, 1533601,
1533961, 1534541, 1537381, 1549411, 1569457, 1579249, 1584133, 1608465,
1615681, 1620385, 1643665, 1678541, 1690501, 1711381, 1719601, 1730977,
1735841, 1746289, 1755001, 1773289, 1801969, 1809697, 1811573, 1815465,
1826203, 1827001, 1830985, 1837381, 1839817, 1840357, 1857241, 1876393,
1892185, 1896961, 1907851, 1908985, 1909001, 1937881, 1969417, 1987021,
1993537, 1994689, 2004403, 2008597, 2035153, 2077545, 2081713, 2085301,
2089297, 2100901, 2113665, 2113921, 2121301, 2134277, 2142141, 2144521,
2162721, 2163001, 2165801, 2171401, 2181961, 2184571, 2205967, 2213121,
2232865, 2233441, 2261953, 2264369, 2269093, 2284453, 2288661, 2290641,
2299081, 2304167, 2313697, 2327041, 2350141, 2387797, 2414001, 2419385,
2433601, 2434651, 2455921, 2487941, 2491637, 2503501, 2508013, 2510569,
2513841, 2528921, 2531845, 2537641, 2603381, 2609581, 2615977, 2617451,
2626177, 2628073, 2649029, 2649361, 2670361, 2704801, 2719981, 2722681,
2746477, 2746589, 2748023, 2757241, 2773981, 2780731, 2793351, 2797921,
2811271, 2827801, 2867221, 2880361, 2882265, 2899801, 2909197, 2921161,
2940337, 2944261, 2953711, 2976487, 2977217, 2987167, 3020361, 3048841,
3057601, 3059101, 3073357, 3090091, 3094273, 3116107, 3125281, 3146221,
3165961, 3181465, 3186821, 3224065, 3225601, 3235699, 3316951, 3336319,
3337849, 3345773, 3363121, 3370641, 3375041, 3375487, 3400013, 3413533,
3429037, 3435565, 3471071, 3539101, 3542533, 3567481, 3568661, 3581761,
3605429, 3656449, 3664585, 3679201, 3726541, 3746289, 3755521, 3763801,
3779185, 3814357, 3828001, 3898129, 3911197, 3916261, 3936691, 3985921,
4005001, 4014361, 4025905, 4038673, 4069297, 4072729, 4082653, 4097791,
4101637, 4151869, 4154161, 4154977, 4181921, 4188889, 4209661, 4229601,
4259905, 4314967, 4335241, 4360621, 4361389, 4363261, 4371445, 4415251,
4463641, 4469471, 4480477, 4502485, 4504501, 4513841, 4535805, 4567837,
4613665, 4650049, 4670029, 4682833, 4698001, 4706821, 4714201, 4767841,
4806061, 4827613, 4835209, 4863127, 4864501, 4868701, 4869313, 4877641,
4895065, 4903921, 4909177, 4917331, 4917781, 4922413, 4974971, 4984001,
5016191, 5031181, 5034601, 5044033, 5049001, 5095177, 5131589, 5133201,
5148001, 5173169, 5173601, 5176153, 5187637, 5193721, 5250421, 5256091,
5258701, 5271841, 5284333, 5310721, 5351537, 5400489, 5423713, 5444489,
5456881, 5481451, 5489121, 5489641, 5524693, 5529745, 5545145, 5551201,
5560809, 5575501, 5590621, 5599765, 5632705, 5672041, 5681809, 5733649,
5758273, 5766001, 5804821, 5859031, 5872361, 5919187, 5968261, 5968873,
5977153, 6027193, 6049681, 6054985, 6118141, 6122551, 6135585, 6140161,
6159301, 6183601, 6189121, 6212361, 6226193, 6233977, 6235345, 6236257,
6236473, 6242685, 6255341, 6278533, 6309901, 6313681, 6334351, 6350941,
6368689, 6386993, 6474691, 6539527, 6617929, 6628385, 6631549, 6658669,
6732817, 6733693, 6749021, 6779137, 6787327, 6836233, 6840001, 6868261,
6886321, 6912079, 6952037, 6955541, 6973057, 6973063, 6998881, 7008001,
7017193, 7040001, 7177105, 7207201, 7215481, 7232321, 7233265, 7259161,
7273267, 7295851, 7306261, 7306561, 7414333, 7416289, 7428421, 7429117,
7455709, 7462001, 7516153, 7519441, 7546981, 7656721, 7674967, 7693401,
7724305, 7725901, 7759937, 7803769, 7808593, 7814401, 7820201, 7883731,
7995169, 8012845, 8036033, 8041345, 8043841, 8095447, 8134561, 8137585,
8137633, 8180461, 8209657, 8231653, 8239477, 8280229, 8321671, 8322945,
8341201, 8355841, 8362201, 8384513, 8388607, 8462233, 8534233, 8640661,
8646121, 8650951, 8656705, 8719309, 8719921, 8725753, 8727391, 8745277,
8812273, 8830801, 8902741, 8916251, 8927101, 8992201, 9006401, 9037729,
9040013, 9046297, 9056501, 9063105, 9069229, 9073513, 9084223, 9106141,
9131401, 9143821, 9223401, 9224391, 9273547, 9345541, 9371251, 9439201,
9480461, 9494101, 9533701, 9564169, 9567673, 9582145, 9585541, 9588151,
9591661, 9613297, 9638785, 9692453, 9724177, 9729301, 9774181, 9816465,
9834781, 9863461, 9890881, 9908921, 9920401, 9995671, 10004681, 10024561,
10031653, 10033777, 10079521, 10084177, 10134601, 10185841, 10226161, 10239985,
10251473, 10266001, 10267951, 10275685, 10317601, 10323769, 10331141, 10386241,
10393201, 10402237, 10402561, 10403641, 10425511, 10505701, 10513261, 10545991,
10606681, 10610063, 10635751, 10655905, 10680265, 10700761, 10712857, 10763653,
10802017, 10818505, 10837321, 10877581, 10956673, 10958221, 10974385, 10974881,
11034365, 11075857, 11081459, 11115037, 11119105, 11157721, 11205601, 11242465,
11328409, 11335501, 11367137, 11433301, 11473885, 11541307, 11585293, 11592397,
11644921, 11767861, 11776465, 11777599, 11875821, 11921001, 11972017, 12032021,
12067705, 12096613, 12261061, 12262321, 12263131, 12273769, 12322133, 12327121,
12376813, 12407011, 12490201, 12498061, 12584251, 12599233, 12643381, 12659989,
12702145, 12711007, 12757361, 12783811, 12854437, 12932989, 12936763, 12939121,
12945745, 12979765, 13057787, 13073941, 13187665, 13216141, 13295281, 13333441,
13338371, 13357981, 13421773, 13446253, 13448593, 13500313, 13554781, 13635289,
13635649, 13694761, 13696033, 13747361, 13757653, 13773061, 13823601, 13838569,
13856417, 13899565, 13942081, 13971841, 13991647, 13992265, 13996951, 14012797,
14026897, 14154337, 14179537, 14282143, 14324473, 14469841, 14556081, 14589901,
14609401, 14671801, 14676481, 14684209, 14709241, 14794081, 14796289, 14865121,
14870801, 14885697, 14892153, 14898631, 14899751, 14913991, 14980411, 15082901,
15101893, 15124969, 15139199, 15162941, 15188557, 15207361, 15220951, 15247621,
15248773, 15268501, 15403285, 15472441, 15479777, 15510041, 15525241, 15560461,
15583153, 15603391, 15621409, 15698431, 15700301, 15716041, 15732721, 15757741,
15802681, 15829633, 15888313, 15913261, 15976747, 15978007, 16046641, 16053193,
16070429, 16132321, 16149169, 16149601, 16153633, 16158331, 16263105, 16324001,
16349477, 16360381, 16435747, 16539601, 16666651, 16705021, 16717061, 16773121,
16778881, 16818877, 16822081, 16843009, 16853077, 16879501, 16973393, 16998961,
17020201, 17098369, 17116837, 17134043, 17208601, 17236801, 17316001, 17327773,
17375249, 17405537, 17429861, 17450569, 17509501, 17585969, 17586361, 17590957,
17641207, 17698241, 17759681, 17777191, 17812081, 17870561, 17895697, 18003349,
18007345, 18067501, 18073817, 18137505, 18151861, 18162001, 18300241, 18307381,
18366937, 18443701, 18454921, 18468901, 18487267, 18490381, 18535177, 18541441,
18595801, 18607009, 18653353, 18736381, 18740971, 18779761, 18900973, 18985627,
19020191, 19054933, 19092921, 19149571, 19260865, 19328653, 19384289, 19404139,
19471033, 19523505, 19569265, 19607561, 19683001, 19734157, 19781763, 19985269,
20081953, 20099017, 20117467, 20140129, 20202481, 20234341, 20261251, 20417311,
20489239, 20494401, 20626165, 20647621, 20770621, 20964961, 20968501, 21042001,
21224401, 21303343, 21306157, 21355951, 21359521, 21397381, 21400481, 21414169,
21417991, 21459361, 21474181, 21559741, 21584305, 21585313, 21623659, 21654533,
21715681, 21789901, 21814417, 21880801, 21907009, 22066201, 22075579, 22087477,
22137809, 22203181, 22215961, 22269745, 22351249, 22369621, 22397497, 22432201,
22480381, 22487101, 22509691, 22513457, 22564081, 22591301, 22665505, 22669501,
22711873, 22848541, 22849481, 22885129, 22899097, 22953673, 23054601, 23247901,
23261713, 23283037, 23286781, 23315977, 23382529, 23386441, 23405341, 23464033,
23517985, 23577497, 23634181, 23734901, 23736385, 23808721, 23822329, 23828017,
23872213, 23963869, 23966011, 24037021, 24158641, 24161905, 24214051, 24356377,
24726773, 24776557, 24904153, 24913681, 24929281, 25080101, 25150501, 25266745,
25270105, 25276421, 25326001, 25457833, 25520833, 25540291, 25557121, 25603201,
25629913, 25640641, 25696133, 25768261, 25831585, 25840081, 25846913, 25873381,
25909453, 25947959, 26254801, 26280073, 26296401, 26377921, 26465089, 26470501,
26474581, 26553241, 26634301, 26719701, 26758057, 26813221, 26821601, 26840269,
26877421, 26886817, 26921089, 26932081, 26977001, 27032545, 27062101, 27108397,
27118601, 27128201, 27168337, 27218269, 27219697, 27271151, 27279409, 27331921,
27336673, 27380831, 27392041, 27401401, 27402481, 27409541, 27476641, 27491237,
27492581, 27509653, 27600001, 27664033, 27700609, 27714961, 27736345, 27798461,
27808463, 27846721, 27966709, 27986421, 28011001, 28029001, 28071121, 28172629,
28175001, 28312921, 28325881, 28406953, 28449961, 28527049, 28572961, 28629613,
28717483, 28787185, 29020321, 29111881, 29137021, 29143633, 29214541, 29581501,
29593159, 29732221, 29878381, 30022129, 30058381, 30069721, 30090817, 30185569,
30219757, 30295141, 30296761, 30338593, 30388753, 30411201, 30418957, 30529693,
30576151, 30653245, 30662497, 30718441, 30739969, 30740417, 30881551, 30894307,
30951181, 30958201, 30971161, 30992401, 30996001, 31040833, 31118221, 31146661,
31150351, 31166803, 31198693, 31405501, 31436123, 31692805, 31735621, 31759121,
31766983, 31794241, 31880577, 32080651, 32091781, 32095057, 32158621, 32168117,
32264029, 32285041, 32368609, 32428045, 32497921, 32676481, 32701297, 32756581,
32899201, 32914441, 33018985, 33146717, 33193117, 33298337, 33302401, 33408145,
33596641, 33600533, 33627301, 33704101, 33840397, 33848311, 33872593, 33965261,
34003061, 34043101, 34100821, 34111441, 34124641, 34196401, 34386121, 34487601,
34540801, 34581457, 34603041, 34657141, 34856167, 34890481, 34901461, 34944001,
35428141, 35498467, 35571601, 35576599, 35626501, 35703361, 35820937, 35851037,
35926801, 35932441, 35967921, 35976721, 36121345, 36168265, 36255451, 36291193,
36307981, 36338653, 36354449, 36448387, 36507801, 36721021, 36724591, 36765901,
36852481, 36861901, 36919681, 36942157, 36974341, 36981601, 37109467, 37167361,
37280881, 37354465, 37376509, 37439201, 37469701, 37491301, 37695505, 37727341,
37769887, 37938901, 37962541, 37964809, 37988497, 38010307, 38046817, 38118763,
38151361, 38171953, 38210323, 38239741, 38342071, 38404501, 38439523, 38453151,
38560861, 38584801, 38624041, 38637361, 38789913, 38790753, 38801089, 38903287,
38971661, 39016741, 39052333, 39117439, 39126313, 39353665, 39465091, 39467377,
39512773, 39573073, 39655153, 39684157, 39789841, 40094341, 40160737, 40165093,
40238797, 40280065, 40315441, 40325041, 40361197, 40374901, 40430401, 40622401,
40629601, 40778989, 40782589, 40801861, 40827473, 40841821, 40886241, 40917241,
40928701, 40933705, 40987201, 41017681, 41067665, 41073241, 41102601, 41121433,
41262073, 41298985, 41341321, 41396921, 41424801, 41471521, 41541241, 41568101,
41590297, 41604109, 41607721, 41642681, 41662297, 41840809, 41866001, 41987111,
42009217, 42344609, 42485119, 42490801, 42623017, 42689305, 42694279, 42697873,
42702661, 42709591, 42763501, 42984589, 42998901, 43039501, 43136821, 43224397,
43235641, 43286881, 43331401, 43363601, 43397551, 43584481, 43620409, 43661257,
43798457, 43914949, 44070841, 44081101, 44238481, 44314129, 44347381, 44465221,
44472001, 44482901, 44521301, 44671001, 44695211, 44731051, 44823241, 44824501,
44912701, 44953441, 44963029, 45100177, 45175201, 45219329, 45318561, 45393601,
45414433, 45485881, 45563027, 45593065, 45769645, 45819541, 45830161, 45877861,
45879941, 45890209, 46045117, 46055851, 46094401, 46104697, 46256489, 46282405,
46325029, 46386589, 46469809, 46483633, 46517857, 46647745, 46657181, 46679761,
46860001, 46878601, 47006785, 47063611, 47220367, 47253781, 47349373, 47356171,
47647117, 47734141, 47744209, 47759041, 47903701, 47918581, 47930023, 47953621,
48064021, 48191653, 48269761, 48277081, 48316321, 48316969, 48321001, 48369727,
48398065, 48400753, 48448661, 48462301, 48506581, 48551161, 48563089, 48592393,
48628801, 48650641, 48656869, 49075417, 49084321, 49303801, 49333201, 49411801,
49430305, 49439237, 49459801, 49472281, 49664207, 50155733, 50176477, 50193793,
50201089, 50376019, 50443201, 50473501, 50523661, 51030601, 51129781, 51283501,
51302353, 51340807, 51396865, 51500521, 51509161, 51627817, 51803821, 51890545,
52018341, 52072021, 52119289, 52142221, 52181407, 52204237, 52365457, 52452905,
52869601, 53154337, 53245921, 53283169, 53315605, 53399449, 53542147, 53560801,
53656021, 53661945, 53675623, 53695721, 53711113, 53728921, 53795521, 54029741,
54060721, 54177949, 54215161, 54448153, 54449431, 54468001, 54545821, 54651961,
54767881, 54772381, 55035001, 55109401, 55176097, 55200181, 55318957, 55324801,
55329985, 55462177, 55610837, 55729957, 55961065, 56052361, 56420033, 56479897,
56608201, 56643181, 56669041, 56687821, 56810137, 57130161, 57172501, 57421219,
57561085, 57707209, 57749185, 57762433, 58003213, 58422409, 58449847, 58489201,
58498105, 58509977, 58679941, 58708761, 58755877, 58903741, 59408497, 59426221,
59469697, 59586241, 59589973, 59631211, 59840537, 59913157, 59953741, 59955331,
59999011, 60112885, 60155201, 60352921, 60375745, 60514129, 60547831, 60558841,
60566431, 60581401, 60696661, 60738257, 60761701, 60769051, 60925879, 60957361,
60998653, 61198921, 61201009, 61219789, 61309333, 61330291, 61377109, 61679905,
61754941, 61755751, 61794709, 61832377, 62176661, 62248649, 62289541, 62490901,
62633371, 62656985, 62756641, 63001801, 63002501, 63065281, 63127681, 63167743,
63294553, 63318169, 63328469, 63337393, 63346999, 63388033, 63526519, 63560685,
63729073, 63781901, 63884521, 63919801, 64009261, 64148717, 64162693, 64238021,
64377991, 64477249, 64567405, 64605041, 64644385, 64685545, 64735897, 64774081,
64940041, 65037817, 65144501, 65241793, 65254393, 65301013, 65350801, 65350821,
65359477, 65427701, 65523781, 65565457, 65919745, 66024901, 66096253, 66296401,
66384121, 66437841, 66760471, 66790057, 66849091, 66886417, 66932851, 66976273,
66977281, 67194401, 67213801, 67371265, 67529437, 67541761, 67559383, 67642513,
67653433, 67763803, 67902031, 67928221, 67940449, 67968385, 67994641, 68033801,
68075177, 68102641, 68154001, 68165761, 68275873, 68512867, 68621701, 68776561,
68800501, 68830021, 68839597, 68958681, 69030901, 69128641, 69176647, 69228967,
69231061, 69331969, 69414301, 69485281, 69612061, 69615793, 69678307, 69705529,
69741001, 69776785, 69885649, 69917371, 70006021, 70030501, 70147561, 70149631,
70195501, 70461331, 70463489, 70484065, 70488001, 70541099, 70561921, 70593931,
70626301, 70695769, 70728121, 70938429, 71040561, 71079661, 71107681, 71479765,
71570017, 71572957, 71711839, 71734417, 71804161, 72108421, 72135505, 72192021,
72286501, 72348409, 72498253, 72543547, 72595951, 72680431, 72734041, 72803809,
72805981, 72884701, 72887585, 73346365, 73439185, 73451665, 73522051, 73562833,
73645001, 73721341, 73988641, 74165065, 74193769, 74217487, 74329399, 74411131,
74658629, 74698345, 74705401, 74874869, 74927161, 74945953, 75140137, 75143251,
75151441, 75187669, 75501793, 75565873, 75676861, 75681541, 75765313, 75836905,
75927853, 76595761, 76704433, 76725091, 76745101, 76923461, 76969621, 77082545,
77295961, 77334769, 77442905, 77477401, 77518981, 77533123, 77576401, 77594653,
77648941, 77812153, 77817979, 77826001, 77858221, 78073801, 78091201, 78120001,
78206917, 78397705, 78526729, 78671651, 78795181, 78844801, 78905989, 78939089,
79398901, 79411201, 79417801, 79464533, 79525261, 79539197, 79624621, 79625701,
79739713, 79786523, 79854409, 79895401, 80142761, 80146909, 80282161, 80375707,
80556337, 80687881, 80787421, 80891009, 80918281, 80927821, 81189433, 81433591,
81445585, 81480601, 81612105, 81638401, 81680941, 81722145, 81789301, 81926461,
81954133, 82023649, 82139471, 82219801, 82268033, 82273201, 82279741, 82416101,
82452061, 82506439, 82847001, 82870517, 82882753, 82929001, 82976181, 82995421,
83058481, 83083001, 83099521, 83103329, 83204801, 83814151, 83966401, 84028407,
84164033, 84234745, 84311569, 84350561, 84375761, 84417985, 84421081, 84487457,
84758389, 84809521, 84998503, 85030921, 85207669, 85328717, 85374577, 85400701,
85519337, 85759147, 85761481, 85823401, 85875361, 86027329, 86067241, 86114117,
86204977, 86438857, 86484269, 86530621, 86559045, 86968981, 86999837, 87211573,
87318001, 87483241, 87499651, 87558127, 87571121, 87694261, 88099339, 88123141,
88256449, 88368853, 88407361, 88466521, 88615801, 88661861, 88689601, 88735921,
88930463, 89148417, 89244901, 89308771, 89670001, 89784581, 89816545, 89896717,
89915365, 89961421, 90014653, 90270613, 90278161, 90341197, 90532141, 90626185,
90665789, 90670861, 90698401, 90803429, 91367431, 91433281, 91453705, 91587289,
91659283, 92027001, 92139433, 92343745, 92438581, 92625121, 92631001, 92645437,
92677273, 92829781, 92974921, 93030145, 93431521, 93473953, 93541537, 93571633,
93591721, 93614521, 93643201, 93677761, 93839201, 93845161, 93869665, 93926197,
93967105, 94316401, 94502701, 94536001, 94790401, 95053249, 95200561, 95423329,
95451361, 95452781, 96135601, 96259681, 96271681, 96386865, 96589585, 96618397,
96653985, 96791881, 96888641, 96895441, 96904081, 96916279, 96925921, 97047301,
97255801, 97420141, 97487785, 97496449, 97655933, 97676723, 97796953, 97863529,
97924217, 98124481, 98523877, 98586541, 98602381, 98735209, 98756281, 99036001,
99115297, 99486889, 99551881, 99789673, 99830641, 99861985, 99898801, 99945007,
99971821, 100017223,
};

#define prime_count 6542
int prime_list[prime_count];

int prime(int x, int sx)
{
if(x == 2) return 1;
if((x & 1) == 0) return 0;

for(int i = 3; i <= sx; i += 2)
if(x % i == 0) return 0;

return 1;
}

int cmp_int(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}

int prime(int x)
{
if(x == 2) return 1;
if((x & 1) == 0) return 0;

if(x < 65536) return bsearch(&x, prime_list, prime_count, sizeof(int), cmp_int) != NULL;

long long k = 2;
int found = 0;
for(int i = 30; i >= 0; i --)
{
if(found) k *= k;
if((x - 1) & (1 << i))
{
k *= (found + 1);
found = 1;
}
k %= x;
}

if(k == 1) return bsearch(&x, pseudoprime_list, pseudoprime_count, sizeof(int), cmp_int) == NULL;
return 0;
}

void print(int x, int y1, int y2, int found)
{
if(y1 > y2)
{
int tmp = y1;
y1 = y2; y2 = tmp;
}

if(found) printf("%d is the sum of %d and %d.\n", x, y1, y2);
else printf("%d is not the sum of two primes!\n", x);
}

int n, p;

int main(void)
{
// freopen("p10311.in", "rt", stdin);
// freopen("p10311.out", "wt", stdout);

// generam toate numerele prime pana la 65535(inclusiv)

n = 3, p = 2;
int count = 1;
prime_list[0] = 2;

for(; n < 65536; n += 2)
{
if(p * p <= n) p ++;
if(prime(n, p)) prime_list[count ++] = n;
}

// acum incepe rezolvarea efectiva a problemei

while(scanf("%d", &n) == 1)
{
if(n & 1)
{
print(n, 2, n - 2, prime(n - 2));
continue;
}

int found = 0;
p = n - (n >> 1);
p++;
while(p < n && !found)
{
if(prime(p) && prime(n - p)) found = 1;
else p ++;
}

print(n, n - p, p, found);
}

// fclose(stdin);
// fclose(stdout);
}
